
from math import inf

class Solution:

    def maxPathSum(self, root):
        ans = -inf

        def dfs(node):

            if not node:
                return 0
            
            l_val = dfs(node.left)
            r_val = dfs(node.right)

            nonlocal ans
            ans = max(ans, l_val + r_val + node.val)

            # 只贡献子节点的左/右半侧+根节点 给上一级使用
            return max(max(l_val, r_val) + node.val, 0)
        
        dfs(root)
        return ans


